#include"Sort.h"
//
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


//插入排序
// 时间复杂度：O(N^2)  什么情况最坏：逆序  最好：顺序有序，O(N)
void InsertSort(int* a, int n)
{
	// [0, n-2]是最后一组待排序列
	// [0,end]是有序，将end+1位置的值插入[0,end]，并使[0，end+1]保持有序
	for (int i = 0; i < n - 1; i++)	//i<n-1是为了防止下面tmp的end+1越界访问
	{
		int end = i;	//待排数列的最后一个被比数
		int tmp = a[end + 1];	//比数	//tmp范围是[1,n-1]
		while (end >= 0)
		{
			if (tmp < a[end])			//只要比数小于前边的被比数
			{
				a[end + 1] = a[end];	//就将当前的被比数向后移
				--end;					//然后再去比较前一个被比数	
			}
			else
			{
				break;	//为了防止前边的数（被比数）都比待排数（比数）大
			}			//循环一直end--，直到不满足条件跳出循环，都没有进入else插入待排数的情况出现
		}				//因此要在循环的外面进行插值，而不是else中。
		a[end + 1] = tmp;	//当进行到这条语句就只有两种可能：待排数为最小和找到了比待排数小的数
	}						//此时都可以将值放到a[end-1]中
}


//希尔排序
// O(N ^ 1.3)
void ShellSort(int* a, int n)
{
	int gap = n;//gap是距离，是每一组中待排数之间的距离，也是每组的第一个待排数的距离
	while (gap > 1)
	{
		// gap > 1时是预排序
		// gap == 1时是插入排序
		gap = gap / 3 + 1;	// +1保证最后一个gap一定是1

		//从这里开始，就是插入排序了，只不过是分成了gap组同时进行
		//当gap等于1的时候，就是把所有数分成一组，也就是上边的插入排序
		for (size_t i = 0; i < n - gap; ++i)	//i < n-gap 依然是防止tmp越界访问
		{
			int end = i;
			int tmp = a[end + gap];	
			while (end >= 0)
			{
				if (tmp < a[end])
				{	
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

//堆排序
void HeapSort(int* a, int n);

//冒泡排序
void BubbleSort(int* a, int n);

//直接选择排序
void SelectSort(int* a, int n);

//快速排序（hoare版）
void QuickSort(int* a, int left, int right);
